// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// go:generate go run genzfunc。go 

// 包排序提供用于排序切片和用户定义集合的原语。
package sort

// 接口的一个实现可以按此包中的例程排序。
// 这些方法通过整数索引引用基础集合的元素。
type Interface interface {
	// Len是集合中的元素数。
	Len() int

	// Less报告索引为i的元素
	// 是否必须在索引为j的元素之前排序。
	// 
	// 如果Less（i，j）和Less（j，i）都为假，则
	// 则索引为i和j的元素被视为相等。
	// Sort可以在最终结果中以任何顺序放置相等的元素，
	// 而Stable保留相等元素的原始输入顺序。
	// 
	// Less必须描述一个传递顺序：
	// -如果Less（i，j）和Less（j，k）都是真的，那么Less（i，k）也必须是真的。如果Less（i，j）和Less（j，k）都为假，那么Less（i，k）也必须为假。
	// 
	// 请注意，当涉及非数字（NaN）值时，浮点比较（float32或float64值上的<运算符）
	// 不是传递顺序。
	// 参见浮动64切片。对于浮点值的正确实现，请使用Less。
	Less(i, j int) bool

	// Swap使用索引i和j交换元素。
	Swap(i, j int)
}

// insertionSort使用插入排序对数据[a:b]进行排序。
func insertionSort(data Interface, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data.Less(j, j-1); j-- {
			data.Swap(j, j-1)
		}
	}
}

// siftDown对数据[lo:hi]实现heap属性。
// 第一个是堆根所在数组的偏移量。
func siftDown(data Interface, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && data.Less(first+child, first+child+1) {
			child++
		}
		if !data.Less(first+root, first+child) {
			return
		}
		data.Swap(first+root, first+child)
		root = child
	}
}

func heapSort(data Interface, a, b int) {
	first := a
	lo := 0
	hi := b - a

	// 在堆的顶部构建最大元素。
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDown(data, i, hi, first)
	}

	// Pop元素，最大的第一个，进入数据的末尾。
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDown(data, lo, i, first)
	}
}

// Quicksort，松散地跟随Bentley和McIlroy，
// “设计排序功能”，SP&E，1993年11月。

// medianoftree将三个值的中值data[m0]、data[m1]、data[m2]移动到data[m1]中。
func medianOfThree(data Interface, m1, m0, m2 int) {
	// 对3个元素进行排序
	if data.Less(m1, m0) {
		data.Swap(m1, m0)
	}
	// 数据[m0]<=data[m1]
	if data.Less(m2, m1) {
		data.Swap(m2, m1)
		// 数据[m0]<=data[m2]和数据[m1]<data[m2]
		if data.Less(m1, m0) {
			data.Swap(m1, m0)
		}
	}
	// 现在数据[m0]<=data[m1]<=data[m2]
}

func swapRange(data Interface, a, b, n int) {
	for i := 0; i < n; i++ {
		data.Swap(a+i, b+i)
	}
}

func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
	m := int(uint(lo+hi) >> 1) // 这样写是为了避免整数溢出。
	if hi-lo > 40 {
		// Tukey的“第九个”，三个中间值的中间值。
		s := (hi - lo) / 8
		medianOfThree(data, lo, lo+s, lo+2*s)
		medianOfThree(data, m, m-s, m+s)
		medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
	}
	medianOfThree(data, lo, m, hi-1)

	// 不变量是：
	// 数据[lo]=pivot（由ChoosePivot设置）
	// 数据[lo<i<a]<pivot 
	// 数据[a<=i<b]<=pivot 
	// 数据[b<=i<c]未经检查的
	pivot := lo
	a, c := lo+1, hi-1

	for ; a < c && data.Less(a, pivot); a++ {
	}
	b := a
	for {
		}
		}
		if b >= c {
			break
		}
		// 数据[b]>pivot；数据[c-1]<=pivot 
		data.Swap(b, c-1)
		b++
		c--
	}
	// 如果hi-c<3，则存在重复项（根据中位数9的属性）。
	// 让我们更保守一点，将边界设置为5。
	protect := hi-c < 5
	if !protect && hi-c < (hi-lo)/4 {
		// 让我们测试一些点是否相等以透视
		dups := 0
		if !data.Less(pivot, hi-1) { // 数据[hi-1]=透视
			data.Swap(c, hi-1)
			c++
			dups++
		}
		if !data.Less(b-1, pivot) { // 数据[b-1]=透视
			b--
			dups++
		}
		// m-lo=（hi-lo）/2>6 
			data.Swap(m, b-1)
			b--
			dups++
		}
		protect = dups > 1
	}
	if protect {
		// 防止大量重复
		// 添加不变量：
		// 数据[a<=i<b]未检查
		// 数据[b<=i<c]=pivot 
		for {
			for ; a < b && !data.Less(b-1, pivot); b-- { // 数据[b]==pivot 
			}
			for ; a < b && data.Less(a, pivot); a++ { // 数据[a]<pivot 
			}
			if a >= b {
				break
			}
			// 数据[a]=pivot；数据[b-1]<pivot-
			data.Swap(a, b-1)
			a++
			b--
		}
	}
	// 将pivot交换到中间
	data.Swap(pivot, b-1)
	return b - 1, c
}

func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 { // 对片使用ShellSort<=12个元素
		if maxDepth == 0 {
			heapSort(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot(data, a, b)
		// 避免在较大的子问题上递归保证
		// 堆栈深度最多为lg（b-a）。
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // 即快速排序（数据，mhi，b）
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // 即快速排序（数据，a，mlo）
		}
	}
	if b-a > 1 {
		// 使用gap 6进行ShellSort传递
		// 可以用这种简化形式编写，原因是b-a<=12 
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort(data, a, b)
	}
}

// 按Less方法确定的升序对数据进行排序。
// 它只调用一次数据。Len确定对
// 数据的n和O（n*log（n））调用。更少的信息和数据。交换这类产品不能保证稳定。
func Sort(data Interface) {
	n := data.Len()
	quickSort(data, 0, n, maxDepth(n))
}

// maxDepth返回一个阈值，在该阈值下，quicksort应将
// 切换到heapsort。它返回2*ceil（lg（n+1））。
func maxDepth(n int) int {
	var depth int
	for i := n; i > 0; i >>= 1 {
		depth++
	}
	return depth * 2
}

// lessSwap是一对Less and Swap函数，用于
// 自动生成的函数优化排序变量。进入
// zfuncversion。去
type lessSwap struct {
	Less func(i, j int) bool
	Swap func(i, j int)
}

type reverse struct {
	// 此嵌入式接口允许反向使用
	// 另一个接口实现的方法。
	Interface
}

// Less返回与嵌入式实现的Less方法相反的结果。
func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

// Reverse返回数据的相反顺序。
func Reverse(data Interface) Interface {
	return &reverse{data}
}

// IsSorted报告数据是否已排序。
func IsSorted(data Interface) bool {
	n := data.Len()
	for i := n - 1; i > 0; i-- {
		if data.Less(i, i-1) {
			return false
		}
	}
	return true
}

// 常见情况的便利类型

// IntSlice将接口方法附加到[]int，并按递增顺序排序。
type IntSlice []int

func (x IntSlice) Len() int           { return len(x) }
func (x IntSlice) Less(i, j int) bool { return x[i] < x[j] }
func (x IntSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

// Sort是一种方便的方法：x.Sort（）调用Sort（x）。
func (x IntSlice) Sort() { Sort(x) }

// Float64Slice为[]float64实现接口，按递增顺序排序，
// 非数字（NaN）值排序在其他值之前。
type Float64Slice []float64

func (x Float64Slice) Len() int { return len(x) }

// Less根据排序接口的要求，报告x[i]是否应该在x[j]之前排序。
// 请注意，浮点比较本身不是传递关系：它不报告非数字（NaN）值的一致顺序。
// 这个实现将NaN值放在任何其他值之前的位置更少，方法是使用：
// 
// x[i]<x[j]|（math.IsNaN（x[i]）&！数学IsNaN（x[j]）
// 
func (x Float64Slice) Less(i, j int) bool { return x[i] < x[j] || (isNaN(x[i]) && !isNaN(x[j])) }
func (x Float64Slice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

// IsNaN是数学的副本。IsNaN避免了对数学软件包的依赖。
func isNaN(f float64) bool {
	return f != f
}

// Sort是一种方便的方法：x.Sort（）调用Sort（x）。
func (x Float64Slice) Sort() { Sort(x) }

// StringSlice将接口方法附加到[]字符串，按递增顺序排序。
type StringSlice []string

func (x StringSlice) Len() int           { return len(x) }
func (x StringSlice) Less(i, j int) bool { return x[i] < x[j] }
func (x StringSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

// Sort是一种方便的方法：x.Sort（）调用Sort（x）。
func (x StringSlice) Sort() { Sort(x) }

// 常见情况下的便利包装

// Ints按递增顺序对一片Ints进行排序。
func Ints(x []int) { Sort(IntSlice(x)) }

// Float64s按递增顺序对Float64s的一部分排序。
// 非数字（NaN）值在其他值之前排序。
func Float64s(x []float64) { Sort(Float64Slice(x)) }

// Strings按递增顺序对字符串片段排序。
func Strings(x []string) { Sort(StringSlice(x)) }

// IntsAreSorted报告切片x是否按递增顺序排序。
func IntsAreSorted(x []int) bool { return IsSorted(IntSlice(x)) }

// Float64sAreSorted报告切片x是否按递增顺序排序，
// 在任何其他值之前使用非数字（NaN）值。
func Float64sAreSorted(x []float64) bool { return IsSorted(Float64Slice(x)) }

// StringsResorted报告切片x是否按递增顺序排序。
func StringsAreSorted(x []string) bool { return IsSorted(StringSlice(x)) }

// 关于稳定排序的注意事项：
// 使用的算法简单且可证明对所有输入都是正确的，并且只使用对数附加堆栈空间。如果通过实验将
// 与其他稳定的就地排序算法进行比较，它们的性能良好。
// 
// 对其他算法评估的评论：
// /-GCC的4.6.3稳定的_排序，不带libstdc++的_缓冲区：
// 没有更快。
// /-GCC的_旋转块旋转：不更快。
// /-“实用就地合并排序”，来自Jyrki Katajainen、Tomi A.Pasanen和Jukka Teuhola；Nordic Journal of Computing 3,1（1996），27-40:
// 给定的算法已就位，交换和分配的数量
// 随着n log n的增加而增加，但算法不稳定。
// /-“O（n）数据移动的快速稳定就地排序”J.I.Munro和
// /V.Raman In Algorithmica（1996）16，115-160:
// 此算法需要额外的2n位，或者仅当
// 有足够多的不同元素可用于编码某些置换
// 之后必须撤消（因此在任何输入上都不稳定）时才有效。
// -我发现的所有最佳就地排序/合并算法要么是
// 不稳定，要么在每个步骤中依赖足够多的不同元素来编码
// 执行的块重排。另见“就地合并算法”，
// Denham Coates Evely，国王学院计算机科学系，
// 2004年1月及其参考文献。
// -通常“最优”算法在赋值数量上是最优的，但接口只有交换操作。

// 稳定按Less方法确定的升序对数据进行排序，
// 同时保持相等元素的原始顺序。
// 
// 它对数据进行一次调用。Len确定对
// 数据的n，O（n*log（n））调用。Less和O（n*log（n）*log（n））调用数据。交换
func Stable(data Interface) {
	stable(data, data.Len())
}

func stable(data Interface, n int) {
	blockSize := 20 // 必须大于0 
	a, b := 0, blockSize
	for b <= n {
		insertionSort(data, a, b)
		a = b
		b += blockSize
	}
	insertionSort(data, a, n)

	for blockSize < n {
		a, b = 0, 2*blockSize
		for b <= n {
			symMerge(data, a, a+blockSize, b)
			a = b
			b += 2 * blockSize
		}
		if m := a + blockSize; m < n {
			symMerge(data, a, m, n)
		}
		blockSize *= 2
	}
}

// symMerge使用
// Pok Son Kim和Arne Kutzner的symMerge算法“稳定最小
// 通过对称比较进行存储合并”，在Susanne Albers和Tomasz 
// Radzik，编辑，算法-ESA 2004，第3221卷
// 计算机科学，第714-723页。Springer，2004。
// 
// 让M=M-a和N=b-N。Wolog M<N。
// 递归深度受ceil（对数（N+M）约束).
// 该算法需要对数据进行O（M*log（N/M+1））调用。较少的
// 该算法需要对数据进行O（（M+N）*log（M））调用。交换
// 
// 本文给出了O（（M+N）*log（M））作为假设
// 使用O（M+N+gcd（M+N））赋值的旋转算法的赋值数。本文对
// 交换操作进行了论证，特别是当块
// 交换旋转仅使用O（M+N）交换时。
// 
// symMerge假设非退化参数：a<m&&m<b.
// 让调用方检查此条件可消除许多叶递归调用，从而提高性能。
func symMerge(data Interface, a, m, b int) {
	// 如果数据[a:m]只包含一个元素，则直接将数据[a]插入数据[m:b]
	// 以避免不必要的对称递归。
	if m-a == 1 {
		// 使用二进制搜索查找最低索引i 
		// 这样m<=i<b的数据[i]>=data[a]。
		// 如果不存在这样的索引，则以i==b退出搜索循环。
		i := m
		j := b
		for i < j {
			h := int(uint(i+j) >> 1)
			if data.Less(h, a) {
				i = h + 1
			} else {
				j = h
			}
		}
		// 交换值，直到数据[a]到达i之前的位置。
		for k := a; k < i-1; k++ {
			data.Swap(k, k+1)
		}
		return
	}

	// 如果数据[m:b]只包含一个元素，则直接将数据[m]插入数据[a:m]
	// 以避免不必要的对称递归。
	if b-m == 1 {
		// 使用二进制搜索查找最低索引i 
		// 这样，a<=i<m的数据[i]>data[m]。如果不存在这样的索引，则使用i==m退出搜索循环。
		i := a
		j := m
		for i < j {
			h := int(uint(i+j) >> 1)
			if !data.Less(m, h) {
				i = h + 1
			} else {
				j = h
			}
		}
		// 交换值，直到数据[m]到达位置i。
		for k := m; k > i; k-- {
			data.Swap(k, k-1)
		}
		return
	}

	mid := int(uint(a+b) >> 1)
	n := mid + m
	var start, r int
	if m > mid {
		start = n - b
		r = mid
	} else {
		start = a
		r = m
	}
	p := n - 1

	for start < r {
		c := int(uint(start+r) >> 1)
		if !data.Less(p-c, c) {
			start = c + 1
		} else {
			r = c
		}
	}

	end := n - start
	if start < m && m < end {
		rotate(data, start, m, end)
	}
	if a < start && start < mid {
		symMerge(data, a, start, mid)
	}
	if mid < end && end < b {
		symMerge(data, mid, end, b)
	}
}

// 旋转数据中的两个连续块u=data[a:m]和v=data[m:b]：
// 格式为'x u v y'的数据更改为'x v u y'。
// rotate最多执行b-a多个数据调用。Swap，
// 它假设非退化参数：a<m&&m<b.
func rotate(data Interface, a, m, b int) {
	i := m - a
	j := b - m

	for i != j {
		if i > j {
			swapRange(data, m-i, m, j)
			i -= j
		} else {
			swapRange(data, m-i, m+j-i, i)
			j -= i
		}
	}
	// i==j 
	swapRange(data, m-i, m, i)
}

/*
Complexity of Stable Sorting


Complexity of block swapping rotation

Each Swap puts one new element into its correct, final position.
Elements which reach their final position are no longer moved.
Thus block swapping rotation needs |u|+|v| calls to Swaps.
This is best possible as each element might need a move.

Pay attention when comparing to other optimal algorithms which
typically count the number of assignments instead of swaps:
E.g. the optimal algorithm of Dudzinski and Dydek for in-place
rotations uses O(u + v + gcd(u,v)) assignments which is
better than our O(3 * (u+v)) as gcd(u,v) <= u.


Stable sorting by SymMerge and BlockSwap rotations

SymMerg complexity for same size input M = N:
Calls to Less:  O(M*log(N/M+1)) = O(N*log(2)) = O(N)
Calls to Swap:  O((M+N)*log(M)) = O(2*N*log(N)) = O(N*log(N))

(The following argument does not fuzz over a missing -1 or
other stuff which does not impact the final result).

Let n = data.Len(). Assume n = 2^k.

Plain merge sort performs log(n) = k iterations.
On iteration i the algorithm merges 2^(k-i) blocks, each of size 2^i.

Thus iteration i of merge sort performs:
Calls to Less  O(2^(k-i) * 2^i) = O(2^k) = O(2^log(n)) = O(n)
Calls to Swap  O(2^(k-i) * 2^i * log(2^i)) = O(2^k * i) = O(n*i)

In total k = log(n) iterations are performed; so in total:
Calls to Less O(log(n) * n)
Calls to Swap O(n + 2*n + 3*n + ... + (k-1)*n + k*n)
   = O((k/2) * k * n) = O(n * k^2) = O(n * log^2(n))


Above results should generalize to arbitrary n = 2^k + p
and should not be influenced by the initial insertion sort phase:
Insertion sort is O(n^2) on Swap and Less, thus O(bs^2) per block of
size bs at n/bs blocks:  O(bs*n) Swaps and Less during insertion sort.
Merge sort iterations start at i = log(bs). With t = log(bs) constant:
Calls to Less O((log(n)-t) * n + bs*n) = O(log(n)*n + (bs-t)*n)
   = O(n * log(n))
Calls to Swap O(n * log^2(n) - (t^2+t)/2*n) = O(n * log^2(n))

*/
